1. Technical Field
The present invention relates to a statistical shape model, and to the parameterization of a set of shapes used for the statistical shape model.
2. Related Art
Statistical models of shape have been used for some time to provide automated interpretation of images. See, for example, Cootes, T, A. Hill, and C. Taylor, The use of Active shape models for locating structures in medical images. Image and Vision Computing, 1994, 12: p. 355-366. The basic idea used by the models is to establish, from a training set, a pattern of “legal” variation in the shapes and spatial relationships of structures on a given class of images (the class of images may be for example face images, or hand images, etc.). Statistical analysis is used to give an efficient parametensation of the pattern of legal variation, providing a compact representation of shape. The statistical analysis also provides shape constraints which are used to determine whether the shape of a structure in an analysed image is a plausible example of the object class of interest. See, for example: Coates, T., et al., Active shape models—the training and application, Computer Vision and Image Understanding, 1995. 61: p. 38-59.
One of the main drawbacks to statistical shape models is the need, during training, to establish dense correspondence between shape boundaries for a reasonably large set of example images. It is important to establish the ‘correct’ correspondence, i.e. a landmark should represent the same location for each of the images used to generate the model (for example a landmark could be located at the inner corner of the left eye). If ‘correct’ correspondences are not established, an inefficient model of shape can result, leading to difficulty in defining shape constraints. In other words, the model will not correctly determine whether the shape of a hypothesised structure in an analysed image represents a plausible example of the object class of interest. The problem of establishing correspondence can be viewed as one of finding an appropriate parameterisation of the shape. The term parameterisation refers to the process of defining a one-to-one correspondence between values of one or more parameters and position on the shape so that a given value of the parameter (or parameters) defines a unique location on the shape. For example, a single parameter can define position around a closed boundary, whilst two parameters are required to define position on a closed surface (in 3D) of spherical topology.
In practice, correspondence has been established for training images by using manually defined ‘landmarks’. In 2D this defines a piecewise linear parameterisation of each shape, with equivalent landmarks for the different shapes corresponding by definition and intermediate sections of shape boundary parameterised as a linear function of path length. Shape models generated in this way have been found to function reasonably well. However, there are several disadvantages associated with manually defining landmarks. Firstly, in a general a large number of images must be annotated in order to generate an accurate model, and manually defining landmarks for each image is very time consuming. A second disadvantage is that manually defining the landmarks unavoidably involves an element of subjective judgement when determining exactly where to locate each landmark, and this will lead to some distortion of the model. The disadvantages are exacerbated when manually defining landmarks for 3-D images, since the number of landmarks per image increases significantly.
The impact of parameterisation upon the generation of a two-dimensional (2D) model is illustrated in the following example:
A 2-D statistical shape model is built from a training set of example shapes/boundaries. Each shape, Si, can (without loss of generality) be represented by a set of (n/2) points sampled along the boundary at equal intervals, as defined by some parameterisation Φi of the boundary path.
Using Procrustes analysis [e.g., see Goodall, C., Procrustes Methods in the Statistical Analysis of Shape. Journal of the Royal Statistical Society, 1991, 53(2): p. 285-339] the sets of points can be rigidly aligned to minimize the sum of squared differences between corresponding points. This allows each shape Si to be represented by an n-dimensional shape vector xi, formed by concatenating the coordinates of its sample points, measured in a standard frame of reference. Using Principal Component analysis, each shape vector can be approximated by a linear model of the formx= x+Pb  (1)where x is the mean shape vector, the columns of P describe a set of orthogonal modes of shape variation and b is a vector of shape parameters. New examples of the class of shapes can be generated by choosing values of b within the range found in the training set. This approach can be extended easily to deal with continuous boundary functions [e.g., see Kotcheff, A. C. W. and C. J. Taylor, Automatic Construction of Eigenshape Models by Direct Optimisation. Medical Image Analysis, 1998, 2: p. 303-314.], but for clarity is limited here to the discrete case.
The utility of the linear model of shape shown in (1) depends on the appropriateness of the set of boundary parameterisations {Φi} that are chosen. An inappropriate choice can result in the need for a large set of modes (and corresponding shape parameters) to approximate the training shapes to a given accuracy and may lead to ‘legal’ values of b generating ‘illegal’ shape instances. For example, consider two models generated from a set of 17 hand outlines. Model A uses a set of parameterisations of the outlines that cause ‘natural’ landmarks such as the tips of the fingers to correspond. Model B uses one such correspondence but then uses a simple path length parameterisation to position the other sample points. The variance of the three most significant modes of models A and B are (1.06, 0.58, 0.30) and (2.19, 0.78, 0.54) respectively. This suggests that model A is more compact than model B. All the example shapes generated by model A using values of b within the range found in the training set of ‘legal’ examples of hands, whilst model B generates implausible examples This is illustrated in FIGS. 1a and 1b. 
The set of parameterisations used for model A were obtained by marking ‘natural’ landmarks manually on each training example, then using simple path length parameterisation to sample a fixed number of equally spaced points between them. This manual mark-up is a time-consuming and subjective process. In principle, the modelling approach extends naturally to 3-D, out in practice manual landmarking becomes impractical.
Several previous attempts have been made to automate model generation [3-6] by the automatic location of landmarks for training images See, for example: Brett. A. D. and C. J. Taylor, A Method ofAutomatic Landmark Generation for 3D PDM Construction. Image and Vision Computing, 2000. 18(9): p. 739-748; Hill, A. and C. Taylor. Automatic Landmark generation for point distribution models in British Machine Vision conference. 1994, Birmingham, England, BMVA Press; Hill, A. and C. J. Taylor. A Framework for automatic landmark identification using a new method of non-rigid correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000; Kotcheff A. C. W. and C. J. Taylor, Automatic Construction of Eigenshape Models by Direct Optimisation. Medical Image Analysis, 1998, 2: p. 303-314. Each of these attempts suffers from disadvantages, as set out below.
Various authors have described attempts to automate the construction of statistical shape models from a set of training shapes. The simplest approach is to select a starting point and equally space landmarks along the boundary of each shape. This is advocated by Baumberg and Hogg, Learning Flexible Models from Image Sequences, in 3rd European Conference on Computer Vision, Stockholm, Sweden. 1994, p. 299-308 but it does not generally result in a satisfactory model. Kelemen et al use spherical harmonic descriptors to parameterize their training shapes. Although it is independent of origin, this is equivalent to an arbitrary parameterisation of the boundary, and it is not based upon a consideration of the optimal arrangement of landmarks.
Benayoun et al. [Adaptive meshes and nonrigid motion computation in International Conference on Pattern Recognition, 1994, Jerusalem, Israel] and Kambhamettu and Goldgof [Point Correspondence Recovery in Non-rigid Motion, in IEEE Conference on Computer Vision and Pattern Recognition, 1992. p. 222-227] use curvature information to select landmark points. However, there is a risk that corresponding points will not lie on regions that have the same curvature. Also, since these methods only consider pairwise correspondences, they may not find the best global solution.
A more robust approach to automatic model building is to tret the task as an optmisation problem. Hill and Taylor [Automatic landmark generation for point distribution in models, in British Machine Vision Conference. 1994. Birmingham, England: BMVA Press.] attempt this by minimizing the total variance of a shape model. They choose to iteratively perform a series of local optmisations, re-building the model at each stage. Unfortunately, this makes the approach prone to becoming trapped in local minima and consequently depends on a good initial estimate of the correct landmark positions. Rangarajan et al [The softassign Procrustes Matching Algorithm, in 15th Conference on in formation Processing in Medical imaging. 1997, p. 29-42] describe a method of shape correspondence that also minimizes the total model variance by simultaneously determining a set of correspondences and the similarity transformation required to register pairs of contours. This method is not based upon a consideration of the optimal arrangement of landmarks.
Bookstein [Landmark Methods for forms without landmarks: morphometrics of group differences in outline shape. Medical Image Analysis. 1997, 1(3): p. 225-243] describes an algorithm for landmarking sets of continuous contours represented as polygons. Points are allowed to move along the contours so as to minimize a bending energy term. The parameterisation is not based upon a consideration of the optimal arrangements of landmarks, and instead the arrangement of the landmarks is merely arbitrary.
Kotcheff and Taylor [Automatic construction of Eigenshape Models by Direct Optimisation. Medical Image Analysis, 1998. 2: p. 303-314] describe an approach which attempts to define a best model in terms of ‘compactness’, as measured by the determinant of the model's covariance matrix. They represented the parameterisation of each of a set of training shapes explicitly, and used a genetic algorithm search to optimize the model with respect to the parameterisation. Although this work showed promise, there were several problems. The objective function, although reasonably intuitive, could not be rigorously justified. The method was described for -D shapes and could not easily be extended to 3-D. It was sometimes difficult to make the optimization converge. A further disadvantage is that a required accuracy value had to be selected in order to make the algorithm work correctly. The choice of accuracy value had a direct impact upon the parameterisation chosen. Consequently, different accuracy values were appropriate for different models, and a user was required to select an accuracy value during initiation of the model.